
//2030.含特定字母的最小子序列
class Solution {
public:
    string smallestSubsequence(string s, int k, char letter, int repetition) {
        //就是一个简单的单调栈,遍历数组,栈中元素是单调递增的即可
        int n=s.size(),all=0;
        for(auto e:s) 
        if(e==letter) all++;

        string ret;   //用数组模拟栈
        int have=0;
        for(int i=0;i<n;i++)
        {
            while(!ret.empty()&&ret.back()>s[i]&&(n-i)+ret.size()>k)  //(n-i)+ret.size()>k保证栈中的元素+后面的元素>k
            {
                if(ret.back()==letter&&have+all==repetition) break;
                if(ret.back()==letter) have--;
                ret.pop_back();
            }
            //判断ret剩余的位置够不够放其他字符
            if(s[i]==letter) have++,all--;     
            if(k-ret.size()==repetition-have&&s[i]!=letter) continue;  
            //k-ret.size()表示字符串还差的字符,repetition-have表示还差的letter字符,如果两者相等说明后面要全放letter字符
            ret.push_back(s[i]);
        }
        ret.resize(k);
        return ret;
    }
};